package com.murphy.algorithm.queue;

/**
 *基于数组实现队列
 * @author dongsufeng
 * @date 2020/9/8 16:29
 * @version 1.0
 */
public class ArrayQueue {
	/**
	 * 第一个位置
	 */
	private int head;
	/**
	 * 最后一个位置的下一个
	 */
	private int last;
	/**
	 * 当前个数
	 */
	private int size;
	/**
	 * 队列大小
	 */
	private int count;

	private String [] items;

	ArrayQueue(int count){
		this.count=count;
		head=0;
		last=0;
		size=0;
		items = new String[count];
	}

	/**
	 * 入队列
	 * 此种方法当last==size时需要重新编排数组，，莫名增加时间复杂度
	 * 由此引入循环队列
	 * @return
	 */
	public boolean enQueue(String item){
		if (count==size){
			return false;
		}
		if (last==count){
			for (int i =0;i<size;i++){
				items[i]=items[head+i];
			}
			head=0;
			last=size;
		}
		items[last]=item;
		++last;
		++size;
		return true;
	}

	/**
	 * 循环队列
	 * @param item
	 * @return
	 */
	public boolean enQueue2(String item){
		if (count == size){
			return false;
		}
		if (last==count){
			last=0;
		}
		items[last]=item;
		++size;
		++last;
		return true;
	}

	/**
	 * 出队列
	 * @return
	 */
	public String deQueue(){
		if (last==head){
			return null;
		}
		String item = items[head];
		++head;
		--size;
		return item;
	}

	public static void main(String[] args) {
		ArrayQueue arrayQueue = new ArrayQueue(5);
		arrayQueue.enQueue2("111");
		arrayQueue.enQueue2("222");
		arrayQueue.enQueue2("333");
		arrayQueue.enQueue2("444");
		arrayQueue.enQueue2("555");
		for (int i = 0;i<3;i++) {
			System.out.println(arrayQueue.deQueue());
		}
		System.out.println(arrayQueue.count);
		System.out.println(arrayQueue.enQueue2("666"));
		arrayQueue.enQueue("777");
		System.out.println(arrayQueue.enQueue2("888"));
		System.out.println(arrayQueue.enQueue2("999"));
	}
}
